{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Value at a Given Index in a Bounded Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有界数组中指定下标处的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你三个正整数 <code>n</code>、<code>index</code> 和 <code>maxSum</code> 。你需要构造一个同时满足下述所有条件的数组 <code>nums</code>（下标 <strong>从 0 开始</strong> 计数）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "\t<li><code>nums[i]</code> 是 <strong>正整数</strong> ，其中 <code>0 &lt;= i &lt; n</code></li>\n",
    "\t<li><code>abs(nums[i] - nums[i+1]) &lt;= 1</code> ，其中 <code>0 &lt;= i &lt; n-1</code></li>\n",
    "\t<li><code>nums</code> 中所有元素之和不超过 <code>maxSum</code></li>\n",
    "\t<li><code>nums[index]</code> 的值被 <strong>最大化</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回你所构造的数组中的 <code>nums[index]</code> 。</p>\n",
    "\n",
    "<p>注意：<code>abs(x)</code> 等于 <code>x</code> 的前提是 <code>x &gt;= 0</code> ；否则，<code>abs(x)</code> 等于 <code>-x</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, index = 2,  maxSum = 6\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>数组 [1,1,<strong>2</strong>,1] 和 [1,2,<strong>2</strong>,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6, index = 1,  maxSum = 10\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= maxSum &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= index &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-value-at-a-given-index-in-a-bounded-array](https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-value-at-a-given-index-in-a-bounded-array](https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n2\\n6', '6\\n1\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        if not head:\n",
    "            return 0\n",
    "        maxValue = float('-inf')\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        fast = head\n",
    "        slow = self.reverseList(slow)\n",
    "        while slow:\n",
    "            maxValue = max(fast.val + slow.val, maxValue)\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return maxValue\n",
    "    def reverseList(self, head:ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        if n[0] == \"-\":\n",
    "            for i, j in enumerate(n):\n",
    "                if j > x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "        else:\n",
    "            for i, j in enumerate(n):\n",
    "                if j < x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "        return n+x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        neg = n[0] == '-'\n",
    "        for c in n:\n",
    "            if c != x and (c < x) ^ neg:\n",
    "                return n.replace(c, x + c, 1)\n",
    "        return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        if n[0] == '-':\n",
    "            for c in n[1:]:\n",
    "                if c > x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "        else:\n",
    "            for c in n:\n",
    "                if c < x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "        return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, ln = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        for i in range(start, ln):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        # 正数：大于等于x的都得放前面，循环直到遇到第一个小于x的\n",
    "        # 负数：小于等于x的都得放前面，循环直到遇到第一个大于x的\n",
    "        x = str(x)\n",
    "        if n[0] != '-':\n",
    "            for c in n:\n",
    "                if c < x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "            return n + x\n",
    "        else:\n",
    "            for c in n:\n",
    "                if c > x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "            return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        for c in n:\n",
    "            if c != x and (c < x) ^ (n[0] == '-'):\n",
    "                return n.replace(c, x + c, 1)\n",
    "        return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        m = len(n)\n",
    "        if n[0] == '-':\n",
    "            i = 1\n",
    "            while i < m and n[i] <= x:\n",
    "                i += 1\n",
    "        else:\n",
    "            i = 0\n",
    "            while i < m and n[i] >= x:\n",
    "                i += 1\n",
    "        return n[:i] + x + n[i:] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, ln = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        for i in range(start, ln):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        flag=0\n",
    "        if n[0]=='-':\n",
    "            flag=1\n",
    "            n=n[1:]\n",
    "        for i,n1 in enumerate(n):         \n",
    "            if int(n1)<x and flag==0:\n",
    "                pre=n[:i]\n",
    "                suf=str(x)+n[i:]\n",
    "                return pre+suf\n",
    "            elif int(n1)>x and flag==1:\n",
    "                pre=\"-\"+n[:i]\n",
    "                suf=str(x)+n[i:]\n",
    "                return pre+suf\n",
    "        return n+str(x) if flag==0 else '-'+n+str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        # 正数：大于等于x的都得放前面，循环直到遇到第一个小于x的\n",
    "        # 负数：小于等于x的都得放前面，循环直到遇到第一个大于x的\n",
    "        x = str(x)\n",
    "        if n[0] == '-':\n",
    "            for c in n[1:]:\n",
    "                if c > x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "            return n + x\n",
    "        else:\n",
    "            for c in n:\n",
    "                if c < x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "            return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        # 正数：大于等于x的都得放前面，循环直到遇到第一个小于x的\n",
    "        # 负数：小于等于x的都得放前面，循环直到遇到第一个大于x的\n",
    "        x = str(x)\n",
    "        if n[0] == '-':\n",
    "            for c in n[1:]:\n",
    "                if c > x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "        else:\n",
    "            for c in n:\n",
    "                if c < x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "        return n + x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        direction = 1\n",
    "        base_ord = ord(\"0\")\n",
    "        i = 0\n",
    "\n",
    "        while i < len(n):\n",
    "            nn = n[i]\n",
    "\n",
    "            if nn == \"-\":\n",
    "                direction = -1\n",
    "                i += 1\n",
    "            else:\n",
    "                if (ord(nn) - base_ord) * direction >= x * direction:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return n[:i] + str(x) + n[i:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = len(n)\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, l):\n",
    "                if x < int(n[i]):\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "        else:\n",
    "            for i in range(l):\n",
    "                if x > int(n[i]):\n",
    "                    return n[:i] + str(x) + n[i:] \n",
    "        return n + str(x)\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, ln = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        for i in range(start, ln):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] != \"-\":\n",
    "            temp = \"\"\n",
    "            for i in range(len(n)):\n",
    "                if int(n[i]) < x:\n",
    "                    temp = n[:i] + str(x) + n[i:]\n",
    "                    return temp\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            for i in range(1, len(n)):\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        direction = 1\n",
    "        base_ord = ord(\"0\")\n",
    "        i = 0\n",
    "\n",
    "        while i < len(n):\n",
    "            nn = n[i]\n",
    "\n",
    "            if nn == \"-\":\n",
    "                direction = -1\n",
    "                i += 1\n",
    "            else:\n",
    "                if (ord(nn) - base_ord) * direction >= x * direction:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return n[:i] + str(x) + n[i:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        if n[0] == \"-\":\n",
    "            for index in range(len(n)):\n",
    "                if n[index] > x:\n",
    "                    return n[:index] + x + n[index:]\n",
    "\n",
    "        else:\n",
    "            for index in range(len(n)):\n",
    "                if n[index] < x:\n",
    "                    return n[:index] + x + n[index:]\n",
    "\n",
    "        return n + x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = len(n)\n",
    "        s ,f = 0,1\n",
    "        # if l <= 0:\n",
    "        #     return 0\n",
    "        if n[0]=='-':\n",
    "            s ,f = 1,-1\n",
    "        #     for i in range(1,l):\n",
    "        #         if int(n[i]) > x:\n",
    "        #             return n[:i] + str(x) +n[i:]\n",
    "        #     return n + str(x)\n",
    "        # else:\n",
    "\n",
    "        #     for i in range(l):\n",
    "        #         if int(n[i]) < x:\n",
    "        #             return n[:i] + str(i) + n[i:]\n",
    "        #     return n +str(x)\n",
    "\n",
    "        for i in range(s,l):\n",
    "            if x*f > int(n[i])*f :\n",
    "                return n[:i] + str(x) +n[i:]\n",
    "        return n + str(x)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        if n[0] == '-':\n",
    "            for c in n[1:]:\n",
    "                if c > x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "        else:\n",
    "            for c in n:\n",
    "                if c < x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "        return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, len_n = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        \n",
    "        for i in range(start, len_n):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, s: str, x: int) -> str:\n",
    "        N = len(s)\n",
    "        if s[0] == '-':\n",
    "            for i in range(1, N):\n",
    "                if int(s[i]) > x:\n",
    "                    res = s[:i] + str(x) + s[i:]\n",
    "                    return res\n",
    "            return s + str(x)\n",
    "        else:\n",
    "            for i in range(N):\n",
    "                if int(s[i]) < x:\n",
    "                    res = s[:i] + str(x) + s[i:]\n",
    "                    return res\n",
    "            return s + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        m = len(n)\n",
    "        x = str(x)\n",
    "        if n[0] != '-':\n",
    "            i = 0\n",
    "            while i < m:\n",
    "                if n[i] < x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "                i += 1\n",
    "            return n + x\n",
    "        else:\n",
    "            i = 1\n",
    "            while i < m:\n",
    "                if n[i] > x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "                i += 1\n",
    "            return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] == '-':\n",
    "            for i, j in enumerate(n[1:], 1):\n",
    "                if j > str(x):\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            for i, j in enumerate(n):\n",
    "                if j < str(x):\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] == '-':\n",
    "            index = 0\n",
    "            for i in range(1,len(n)):\n",
    "                if int(n[i]) > x:\n",
    "                    index = i\n",
    "                    break\n",
    "            if index == 0:\n",
    "                return n+str(x)\n",
    "            else:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        else:\n",
    "            index = -1\n",
    "            for i in range(0,len(n)):\n",
    "                if int(n[i]) < x:\n",
    "                    index = i\n",
    "                    break\n",
    "            if index == -1:\n",
    "                return n+str(x)\n",
    "            elif index == 0:\n",
    "                return str(x) + n\n",
    "            else:\n",
    "                return n[:i] + str(x) + n[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        i, x, m = n[0] == '-', str(x), len(n)\n",
    "        if i:\n",
    "            while i < m and n[i] <= x:\n",
    "                i += 1\n",
    "        else:\n",
    "            while i < m and n[i] >= x:\n",
    "                i += 1\n",
    "        return n[:i] + x + n[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        if n[0] == \"-\":\n",
    "            for i, j in enumerate(n):\n",
    "                if j > x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "        else:\n",
    "            for i, j in enumerate(n):\n",
    "                if j < x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "        return n+x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        \n",
    "        nums=len(n)\n",
    "        if n[0]!='-':\n",
    "            for i in range(nums):\n",
    "                if int(n[i])<x:\n",
    "                    return n[:i]+str(x)+n[i:]\n",
    "            return n+str(x)\n",
    "        else:\n",
    "            for i in range(1,nums):\n",
    "                if int(n[i])>x:\n",
    "                    return '-'+n[1:i]+str(x)+n[i:]\n",
    "            return n+str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        ln = len(n)\n",
    "        if n[0] != '-':\n",
    "            for i in range(ln):\n",
    "                if n[i] < x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "            return n + x\n",
    "        else:\n",
    "            for i in range(1, ln):\n",
    "                if n[i] > x:\n",
    "                    return n[:i] + x + n[i:]\n",
    "            return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, ln = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        for i in range(start, ln):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = str(x)\n",
    "        i = 0\n",
    "        if n[0] != '-':\n",
    "            while i < len(n) and n[i] >= x:\n",
    "                i += 1\n",
    "        else:\n",
    "            i = 1\n",
    "            while i < len(n) and n[i] <= x:\n",
    "                i += 1\n",
    "        return n[:i] + x + n[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start,flag,ln = 0,1,len(n)\n",
    "        if n[0] == '-':\n",
    "            start,flag = 1,-1\n",
    "        for i in range(start,ln):\n",
    "            if x*flag>int(n[i])*flag:\n",
    "                return n[:i]+str(x)+n[i:]\n",
    "        return n+str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] != \"-\":\n",
    "            temp = \"\"\n",
    "            for i in range(len(n)):\n",
    "                if int(n[i]) < x:\n",
    "                    temp = n[:i] + str(x) + n[i:]\n",
    "                    return temp\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            temp = \"\"\n",
    "            for i in range(1, len(n)):\n",
    "                if int(n[i]) > x:\n",
    "                    temp = n[:i] + str(x) + n[i:]\n",
    "                    return temp\n",
    "            return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, ln = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        for i in range(start, ln):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, ln = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        for i in range(start, ln):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        # 正数：大于等于x的都得放前面，循环直到遇到第一个小于x的\n",
    "        # 负数：小于等于x的都得放前面，循环直到遇到第一个大于x的\n",
    "        x = str(x)\n",
    "        if n[0] != '-':\n",
    "            for c in n:\n",
    "                if c < x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "            return n + x\n",
    "        else:\n",
    "            for c in n[1:]:\n",
    "                if c > x:\n",
    "                    return n.replace(c, x + c, 1)\n",
    "            return n + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        \n",
    "        if '-' != n[0]:\n",
    "            for i in range(len(n)):\n",
    "                if x > int(n[i]):\n",
    "                    return n[:i] + str(x) + n[i:]     \n",
    "        else:\n",
    "            for i in range(1, len(n)):\n",
    "                if x < int(n[i]):\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, s: str, x: int) -> str:\n",
    "        N = len(s)\n",
    "        if s[0] == '-':\n",
    "            for i in range(1, N):\n",
    "                if int(s[i]) > x:\n",
    "                    res = s[:i] + str(x) + s[i:]\n",
    "                    return res\n",
    "            return s + str(x)\n",
    "        else:\n",
    "            for i in range(N):\n",
    "                if int(s[i]) < x:\n",
    "                    res = s[:i] + str(x) + s[i:]\n",
    "                    return res\n",
    "            return s + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = len(n)\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, l):\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            for i in range(l):\n",
    "                if int(n[i]) < x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxValue(self, n: str, x: int) -> str:\r\n",
    "        start, flag, ln = 0, 1, len(n)\r\n",
    "        if n[0] == '-':\r\n",
    "            start, flag = 1, -1\r\n",
    "        for i in range(start, ln):\r\n",
    "            if x * flag > int(n[i]) * flag:\r\n",
    "                return n[:i] + str(x) + n[i:]\r\n",
    "        return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start,flag,ln = 0,1,len(n)\n",
    "        if n[0] == '-':\n",
    "            start,flag = 1,-1\n",
    "        for i in range(start,ln):\n",
    "            if x*flag>int(n[i])*flag:\n",
    "                return n[:i]+str(x)+n[i:]\n",
    "        return n+str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        start, flag, ln = 0, 1, len(n)\n",
    "        if n[0] == '-':\n",
    "            start, flag = 1, -1\n",
    "        for i in range(start, ln):\n",
    "            if x * flag > int(n[i]) * flag:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = len(n)\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, l):\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "        for i in range(l):\n",
    "            if int(n[i]) < x:\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        insert_i = len(n)\n",
    "        if n[0]  == '-':\n",
    "            for i in range(1, len(n)):\n",
    "                if x < int(n[i]):\n",
    "                    insert_i = i\n",
    "                    break\n",
    "        else:\n",
    "            for i in range(len(n)):\n",
    "                if x > int(n[i]): \n",
    "                    insert_i = i\n",
    "                    break\n",
    "        print(insert_i)\n",
    "        return n[:insert_i] + str(x) + n[insert_i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] != \"-\":\n",
    "            temp = \"\"\n",
    "            for i in range(len(n)):\n",
    "                if int(n[i]) < x:\n",
    "                    temp = n[:i] + str(x) + n[i:]\n",
    "                    return temp\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            temp = \"\"\n",
    "            for i in range(1, len(n)):\n",
    "                if int(n[i]) > x:\n",
    "                    temp = n[:i] + str(x) + n[i:]\n",
    "                    return temp\n",
    "            return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = len(n)\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, l):\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            for i in range(l):\n",
    "                if int(n[i]) < x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if(n[0] == '-'):\n",
    "            idx = None\n",
    "            for i in range(1,len(n)):\n",
    "                if(x < int(n[i])):\n",
    "                    idx = i \n",
    "                    break\n",
    "            if(idx == None):\n",
    "                return n + str(x)\n",
    "            else:\n",
    "                return n[:idx] + str(x) + n[idx:]\n",
    "        else:\n",
    "            idx = None\n",
    "            for i in range(len(n)):\n",
    "                if(x > int(n[i])):\n",
    "                    idx = i \n",
    "                    break \n",
    "            if(idx == None):\n",
    "                return n + str(x)\n",
    "            else:\n",
    "                return n[:idx] + str(x) + n[idx:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] == \"-\":\n",
    "            m = len(n)\n",
    "            for i in range(1, m):\n",
    "                if n[i] > str(x):\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n+str(x)\n",
    "        \n",
    "        m = len(n)\n",
    "        for i in range(m):\n",
    "            if n[i] < str(x):\n",
    "                return n[:i] + str(x) + n[i:]\n",
    "        return n+str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = len(n)\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, l):\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            for i in range(l):\n",
    "                if int(n[i]) < x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, len(n)):\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            for i in range(len(n)):\n",
    "                if int(n[i]) < x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        # 若 n 是正数\n",
    "        if n[0] != '-':\n",
    "            for i in range(len(n)):\n",
    "                # 找到第一个比 x 小的数字，将 x 插入其前面\n",
    "                if int(n[i]) < x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            # 如果没有找到，就在末尾添加\n",
    "            return n + str(x)\n",
    "        # 若 n 是负数\n",
    "        else:\n",
    "            for i in range(1, len(n)):\n",
    "                # 找到第一个比 x 大的数字，将 x 插入其前面\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            # 如果没有找到，就在末尾添加\n",
    "            return n + str(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] != '-':\n",
    "            for i,num in enumerate(n):\n",
    "                if int(num) < x:\n",
    "                    return (n[:i] + str(x) + n[i:])\n",
    "            return (n + str(x))\n",
    "        else:\n",
    "            for i,num in enumerate(n[1:]):\n",
    "                if int(num) > x:\n",
    "                    return (n[:(i+1)] + str(x) + n[(i+1):])\n",
    "            return (n + str(x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        x = ord(str(x))\n",
    "        nn = len(n)\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, nn):\n",
    "                if ord(n[i]) > x:\n",
    "                    return n[:i]+chr(x)+n[i:]\n",
    "        else:\n",
    "            for i in range(nn):\n",
    "                if ord(n[i]) < x:\n",
    "                    return n[:i]+chr(x)+n[i:]\n",
    "        return n+chr(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = len(n)\n",
    "        if n[0] == '-':\n",
    "            for i in range(1, l):\n",
    "                if int(n[i]) > x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)\n",
    "        else:\n",
    "            for i in range(l):\n",
    "                if int(n[i]) < x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n + str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        flag=0\n",
    "        res=''\n",
    "        if n[0]=='-':\n",
    "            res+='-'\n",
    "            for i in range(1,len(n)):\n",
    "                if flag==0 and int(n[i])>x:\n",
    "                    flag=1\n",
    "                    res+=str(x)\n",
    "                res+=n[i]\n",
    "            if flag==0:\n",
    "                res+=str(x)\n",
    "        else:\n",
    "            for i in range(len(n)):\n",
    "                if flag==0 and int(n[i])<x:\n",
    "                    flag=1\n",
    "                    res+=str(x)\n",
    "                res+=n[i]\n",
    "            if flag==0:\n",
    "                res+=str(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] == \"-\":\n",
    "            r = \"-\"\n",
    "            i = 1\n",
    "            while i < len(n):\n",
    "                if x >= int(n[i]):\n",
    "                    r += n[i]\n",
    "                else:\n",
    "                    r += str(x)\n",
    "                    r += n[i:]\n",
    "                    break\n",
    "                    \n",
    "                i += 1\n",
    "\n",
    "            if i == len(n):\n",
    "                r += str(x)\n",
    "                \n",
    "        else:\n",
    "            r = \"\"\n",
    "            i = 0\n",
    "            while i < len(n):\n",
    "                if x > int(n[i]):\n",
    "                    r += str(x)\n",
    "                    r += n[i:]\n",
    "                    break\n",
    "                else:\n",
    "                    r += n[i]\n",
    "                \n",
    "                i += 1\n",
    "            \n",
    "            if i == len(n):\n",
    "                r += str(x)\n",
    "        \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        if n[0] == \"-\":\n",
    "            i = 1\n",
    "            while i < len(n) and int(n[i]) <= x:\n",
    "                i += 1\n",
    "            n = list(n)\n",
    "            n.insert(i, str(x))\n",
    "            return \"\".join(n)\n",
    "        else:\n",
    "            i = 0\n",
    "            while i < len(n) and int(n[i]) >= x:\n",
    "                i += 1\n",
    "            n = list(n)\n",
    "            n.insert(i, str(x))\n",
    "            return \"\".join(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        num_list = list(n)\n",
    "        if num_list[0] == '-':\n",
    "            for i in range( 1, len(num_list)):\n",
    "                if int( num_list[i] ) > x:\n",
    "                    return n[:i] + str(x) + n[i:] \n",
    "            return n+str(x)\n",
    "        else:\n",
    "            for i in range( 0, len(num_list) ):\n",
    "                if int( num_list[i] ) < x:\n",
    "                    return n[:i] + str(x) + n[i:]\n",
    "            return n+str(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        ans = \"\"\n",
    "        if n[0] == \"-\":\n",
    "            ans+=\"-\"\n",
    "            flag = 0\n",
    "            for c in n[1:]:\n",
    "                if flag==0 and int(c)>int(x):\n",
    "                    ans += str(x)\n",
    "                    flag = 1\n",
    "                ans += c\n",
    "            if flag==0:\n",
    "                ans += str(x)\n",
    "            return ans\n",
    "\n",
    "        flag = 0\n",
    "        for c in n:\n",
    "            if flag==0 and int(c)<int(x):\n",
    "                ans += str(x)\n",
    "                flag = 1\n",
    "            ans += c\n",
    "        if flag==0:\n",
    "            ans += str(x)\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        n = list(n)\n",
    "        if n[0] == '-':\n",
    "            size = len(n)\n",
    "            for i in range(1,size):\n",
    "                if int(n[i]) > x:\n",
    "                    n.insert(i,str(x))\n",
    "                    return ''.join(n)\n",
    "            n.append(str(x))\n",
    "            return ''.join(n)\n",
    "        else:\n",
    "            size = len(n)\n",
    "            for i in range(size):\n",
    "                if int(n[i]) < x:\n",
    "                    n.insert(i,str(x))\n",
    "                    return ''.join(n)\n",
    "            n.append(str(x))\n",
    "            return ''.join(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        n = list(n)\n",
    "        if n[0] == '-':\n",
    "            size = len(n)\n",
    "            for i in range(1,size):\n",
    "                if int(n[i]) > x:\n",
    "                    n.insert(i,str(x))\n",
    "                    return ''.join(n)\n",
    "            n.append(str(x))\n",
    "            return ''.join(n)\n",
    "        else:\n",
    "            size = len(n)\n",
    "            for i in range(size):\n",
    "                if int(n[i]) < x:\n",
    "                    n.insert(i,str(x))\n",
    "                    return ''.join(n)\n",
    "            n.append(str(x))\n",
    "            return ''.join(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        ans = []\n",
    "        if n[0] == \"-\":\n",
    "            ans.append(\"-\")\n",
    "            flag = 0\n",
    "            for c in n[1:]:\n",
    "                if flag==0 and int(c)>int(x):\n",
    "                    ans.append(str(x))\n",
    "                    flag = 1\n",
    "                ans.append(c)\n",
    "            if flag==0:\n",
    "                ans.append(str(x))\n",
    "            return \"\".join(ans)\n",
    "        \n",
    "\n",
    "        flag = 0\n",
    "        for c in n:\n",
    "            if flag==0 and int(c)<int(x):\n",
    "                ans.append(str(x))\n",
    "                flag = 1\n",
    "            ans.append(c)\n",
    "        if flag==0:\n",
    "            ans.append(str(x))\n",
    "\n",
    "        return \"\".join(ans)                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        length=len(n)\n",
    "        lst=[]\n",
    "        for i in range(length):\n",
    "            lst.append(n[i])\n",
    "        if n[0]!=\"-\":\n",
    "            a=0\n",
    "            for j in range(length):\n",
    "                if int(lst[j])<x:\n",
    "                    lst.insert(j,str(x))\n",
    "                    a+=1\n",
    "                    break\n",
    "            if a==0:\n",
    "                lst.append(str(x))\n",
    "        else:\n",
    "            b=0\n",
    "            for k in range(1,length):\n",
    "                if int(lst[k])>x:\n",
    "                    lst.insert(k,str(x))\n",
    "                    b+=1\n",
    "                    break\n",
    "            if b==0:\n",
    "                lst.append(str(x))\n",
    "\n",
    "        return \"\".join(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        length=len(n)\n",
    "        lst=[]\n",
    "        for i in range(length):\n",
    "            lst.append(n[i])\n",
    "        if n[0]!=\"-\":\n",
    "            a=0\n",
    "            for j in range(length):\n",
    "                if int(lst[j])<x:\n",
    "                    lst.insert(j,str(x))\n",
    "                    a+=1\n",
    "                    break\n",
    "            if a==0:\n",
    "                lst.append(str(x))\n",
    "        else:\n",
    "            b=0\n",
    "            for k in range(1,length):\n",
    "                if int(lst[k])>x:\n",
    "                    lst.insert(k,str(x))\n",
    "                    b+=1\n",
    "                    break\n",
    "            if b==0:\n",
    "                lst.append(str(x))\n",
    "\n",
    "        return \"\".join(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: str, x: int) -> str:\n",
    "        l = list(n)\n",
    "        if l[0] == '-':\n",
    "            for i, t in enumerate(l[1:]):\n",
    "                if x < int(t):\n",
    "                    l.insert(i+1, str(x))\n",
    "                    return \"\".join(l)\n",
    "            return n+str(x)\n",
    "        else:\n",
    "            for i, t in enumerate(l):\n",
    "                if x > int(t):\n",
    "                    l.insert(i, str(x))\n",
    "                    return \"\".join(l)\n",
    "            return n+str(x)\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxValue(self, n: str, x: int) -> str:\r\n",
    "        flag = False\r\n",
    "        if n[0]=='-':\r\n",
    "            new_n = list(n[1:])\r\n",
    "            flag =True\r\n",
    "        else:\r\n",
    "            new_n = list(n)\r\n",
    "        x = str(x)\r\n",
    "        if not flag:\r\n",
    "            i = 0\r\n",
    "            while i<len(new_n):\r\n",
    "                if new_n[i]>=x:\r\n",
    "                    i+=1\r\n",
    "                else:\r\n",
    "                    left = new_n[:i]\r\n",
    "                    right = new_n[i:]\r\n",
    "                    left.append(x)\r\n",
    "                    left.extend(right)\r\n",
    "                    return ''.join(left)\r\n",
    "            if i==len(new_n):\r\n",
    "                new_n.append(x)\r\n",
    "                return ''.join(new_n)\r\n",
    "        else:\r\n",
    "            i = 0\r\n",
    "            while i<len(new_n):\r\n",
    "                if new_n[i]<=x:\r\n",
    "                    i+=1\r\n",
    "                else:\r\n",
    "                    left = new_n[:i]\r\n",
    "                    right = new_n[i:]\r\n",
    "                    left.append(x)\r\n",
    "                    left.extend(right)\r\n",
    "                    return '-'+''.join(left)\r\n",
    "            if i== len(new_n):\r\n",
    "                new_n.append(x)\r\n",
    "                return '-'+''.join(new_n)\r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxValue(self, n: str, x: int) -> str:\r\n",
    "        flag = False\r\n",
    "        if len(n)==0:\r\n",
    "            return str(x)\r\n",
    "        if n[0]=='-':\r\n",
    "            flag = True\r\n",
    "            new_n = list(n[1:])\r\n",
    "        else:\r\n",
    "            new_n = list(n)\r\n",
    "        x = str(x)\r\n",
    "        if not flag:\r\n",
    "            i = 0\r\n",
    "            while i<len(new_n):\r\n",
    "                if new_n[i]>=x:\r\n",
    "                    i+=1\r\n",
    "                else:\r\n",
    "                    res = new_n[:i]\r\n",
    "                    res.append(x)\r\n",
    "                    res.extend(new_n[i:])\r\n",
    "                    return ''.join(res)\r\n",
    "            res = new_n\r\n",
    "            res.append(x)\r\n",
    "            return ''.join(res)\r\n",
    "        else:\r\n",
    "            i = 0\r\n",
    "            while i<len(new_n):\r\n",
    "                if new_n[i]<=x:\r\n",
    "                    i+=1\r\n",
    "                else:\r\n",
    "                    res = new_n[:i]\r\n",
    "                    res.append(x)\r\n",
    "                    res.extend(new_n[i:])\r\n",
    "                    return '-'+''.join(res)\r\n",
    "            res = new_n\r\n",
    "            res.append(x)\r\n",
    "            return '-'+''.join(res)\r\n",
    "                    \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int: \n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if self.valid(mid, n, index, maxSum):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "    def valid(self, mid: int, n: int, index: int, maxSum: int) -> bool:\n",
    "        left = index\n",
    "        right = n - index - 1\n",
    "        return mid + self.cal(mid, left) + self.cal(mid, right) <= maxSum\n",
    "\n",
    "    def cal(self, big: int, length: int) -> int:\n",
    "        if length + 1 < big:\n",
    "            small = big - length\n",
    "            return ((big - 1 + small) * length) // 2\n",
    "        else:\n",
    "            ones = length - (big - 1)\n",
    "            return (big - 1 + 1) * (big - 1) // 2 + ones\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        p = index + 1\n",
    "        m = maxSum\n",
    "        def check(mid):\n",
    "            count = 0\n",
    "            if p + mid - 1  > n:\n",
    "                count += (2 * mid - n + p ) * (n - p + 1) / 2\n",
    "            else:\n",
    "                count += (mid + 1) * mid / 2 + (n - p - mid + 1)\n",
    "            if p - mid + 1 <= 0:\n",
    "                count += (mid-1 + mid - p + 1) * (p - 1) / 2\n",
    "            else:\n",
    "                count += mid * (mid - 1) / 2 + (p - mid)\n",
    "            return count<=m\n",
    "\n",
    "\n",
    "        left,right = 1, m - n + 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1)//2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            L, R = 0, 0\n",
    "            if index + 1 <= mid:\n",
    "                L = (mid + mid - index) * (index + 1) // 2\n",
    "            else:\n",
    "                L = (1 + mid) * mid // 2 + (index + 1 - mid)\n",
    "            if n - index <= mid:\n",
    "                R = (mid + (mid - (n - index - 1))) * (n - index) // 2\n",
    "            else:\n",
    "                R = (1 + mid) * mid // 2 + (n - index- mid)\n",
    "            return L + R - mid <= maxSum\n",
    "        l = 1\n",
    "        r = maxSum\n",
    "        while l < r:\n",
    "            mid = l + (r - l + 1 >> 1)\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def sum(x, cnt):\n",
    "            return (x + x - cnt + 1) * cnt // 2 if x >= cnt else (x + 1) * x // 2 + cnt - x\n",
    "\n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if sum(mid - 1, index) + sum(mid, n - index) <= maxSum:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self,n,index,maxSum,k):\n",
    "        left_len = index+1   # 2\n",
    "        right_len = n-index  # 5\n",
    "        if k<left_len: # 3<2\n",
    "            left_num = k*(k+1)/2 + left_len-k\n",
    "        else:\n",
    "            left_num = left_len*(k+k-left_len+1)/2\n",
    "        if k<right_len:\n",
    "            right_num = k*(k+1)/2 + right_len-k\n",
    "        else:\n",
    "            right_num = right_len*(k+k-right_len+1)/2\n",
    "        return maxSum>=(left_num+right_num-k)\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        left = 1\n",
    "        right = maxSum\n",
    "        while(left<right-1):\n",
    "            mid = (left+right)//2\n",
    "            if self.isValid(n,index,maxSum,mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        if self.isValid(n,index,maxSum,right):\n",
    "            return right\n",
    "        else:\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(t, l):\n",
    "    res = 0\n",
    "    if t > l:\n",
    "        res += (t - l + 1 + t) * l // 2\n",
    "    else:\n",
    "        res += (1 + t) * t // 2 + (l - t)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        a, b = index, n - index - 1\n",
    "\n",
    "        def check(mid):\n",
    "            res = mid + f(mid - 1, a) + f(mid - 1, b)\n",
    "            return res <= maxSum\n",
    "        \n",
    "        l, r = 1, maxSum\n",
    "        return bisect_left(range(r + 1), 1, l, key=lambda t: not check(t)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def f(x: int, y: int) -> int:\n",
    "            if x >= y:\n",
    "                return (x - y + 1 + x) * y // 2\n",
    "            return y - x + (1 + x) * x // 2\n",
    "        \n",
    "        left, right = 0, maxSum + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            s = f(mid, index + 1) + f(mid, n - index) - mid\n",
    "            # print(mid, s)\n",
    "            if s <= maxSum:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int: \n",
    "        left = index\n",
    "        right = n - index - 1\n",
    "        if left > right:\n",
    "            left, right = right, left\n",
    "\n",
    "        upper = ((left + 1) ** 2 - 3 * (left + 1)) // 2 + left + 1 + (left + 1) + ((left + 1) ** 2 - 3 * (left + 1)) // 2 + right + 1\n",
    "        if upper >= maxSum:\n",
    "            a = 1\n",
    "            b = -2\n",
    "            c = left + right + 2 - maxSum\n",
    "            return floor(((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a)))\n",
    "\n",
    "        upper = (2 * (right + 1) - left - 1) * left // 2 + (right + 1) + ((right + 1) ** 2 - 3 * (right + 1)) // 2 + right + 1\n",
    "        if upper >= maxSum:\n",
    "            a = 1/2\n",
    "            b = left + 1 - 3/2\n",
    "            c = right + 1 + (-left - 1) * left / 2 - maxSum\n",
    "            return floor(((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a)))\n",
    "\n",
    "        else:\n",
    "            a = left + right + 1\n",
    "            b = (-left ** 2 - left - right ** 2 - right) / 2 - maxSum\n",
    "            return floor(-b / a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def help(x, cnt):\n",
    "            return (x + x - cnt + 1) * cnt // 2 if x >= cnt else (x + 1) * x // 2 + cnt - x\n",
    "        left = 1\n",
    "        right = maxSum + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if help(mid - 1, index) + help(mid, n - index) > maxSum:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        #if help(left) <= maxSum:\n",
    "        #    return left\n",
    "        #else:\n",
    "        return left - 1\n",
    "        #return left, right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        l = index\n",
    "        h = n-1-index\n",
    "        low = maxSum // n\n",
    "        high = maxSum + 1\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            temp = 0\n",
    "            if mid - l > 0:\n",
    "                temp += (mid + mid - l) * (l + 1) // 2\n",
    "            else:\n",
    "                temp += (1 + mid) * mid // 2\n",
    "                temp += (l - mid + 1)\n",
    "            if mid - h > 0:\n",
    "                temp += (mid + mid - h) * (h + 1) // 2\n",
    "            else:\n",
    "                temp += (1 + mid) * mid // 2\n",
    "                temp += (h - mid + 1)\n",
    "            temp -= mid\n",
    "            if temp <= maxSum:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "        return low - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        # True, True, ..., True, False, ..., False\n",
    "        left_num, right_num = index, n - 1 - index\n",
    "\n",
    "        def cal(big, length):\n",
    "            if length + 1 < big:\n",
    "                small = big - length\n",
    "                return (small + big-1) * length // 2\n",
    "            else:\n",
    "                ones = length - (big - 1)\n",
    "                return big * (big - 1) // 2 + ones\n",
    "\n",
    "        def check(x):\n",
    "            return x + cal(x, left_num) + cal(x, right_num) <= maxSum\n",
    "        \n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        \n",
    "        def cal( max_num,length):\n",
    "            if max_num >length:\n",
    "\n",
    "                return (max_num+max_num-length-1)*(length) //2\n",
    "            else:\n",
    "                return (max_num*max_num-max_num)//2 +(length-max_num+1)\n",
    "\n",
    "        left = 1\n",
    "        right = maxSum\n",
    "        while left <right:\n",
    "            mid = (left+right+1)//2\n",
    "            left_len = index\n",
    "            right_le = n-index-1\n",
    "            if cal(mid, left_len)+cal(mid,right_le)+mid<=maxSum:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left\n",
    "            \n",
    "       \n",
    "        #     if index ==n-1:\n",
    "        #         print(left(index,i))\n",
    "        #         if left(index,i)<=maxSum:\n",
    "        #             l = i\n",
    "        #         else:\n",
    "        #             r = i-1\n",
    "        #     elif index ==0:\n",
    "        #         print(right(index,i))\n",
    "        #         if right(index,i)<=maxSum:\n",
    "        #             l = i\n",
    "        #         else:\n",
    "        #             r = i-1\n",
    "        #     else:\n",
    "        #         print(left(index,i)+right(index, i)-i)\n",
    "        #         if left(index,i)+right(index, i)-i<=maxSum:\n",
    "        #             l = i\n",
    "        #         else:\n",
    "        #             r = i-1\n",
    "        # return l\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def sum(x,index):\n",
    "            return x*(x-1)/2 + index + 1 -x if index >= x else (2*x - 1 -index)*index/2\n",
    "        \n",
    "        left , right = 1 , maxSum\n",
    "        while left < right:\n",
    "            mid = (left + right+1)//2\n",
    "            if sum(mid,index) + sum(mid,n - index - 1) + mid <= maxSum:\n",
    "                left = mid\n",
    "            else:right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(m: int) -> bool:\n",
    "            # if m == 0:\n",
    "            #     return True\n",
    "            ans = -m\n",
    "            l = index + 1\n",
    "            if m >= l:\n",
    "                x0 = m - (l - 1)\n",
    "                ans += (x0 + m) * l // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + l - m\n",
    "            \n",
    "            r = n - index\n",
    "            if m >= r:\n",
    "                x0 = m - (r - 1)\n",
    "                ans += (x0 + m) * r // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + r - m\n",
    "            return ans <= maxSum\n",
    "        left = 1\n",
    "        right = maxSum + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        left, right = 1, maxSum\n",
    "        def g(upper, x):\n",
    "            if x + 1 <= upper:\n",
    "                lower = upper - x\n",
    "                return (lower + upper - 1) * x // 2\n",
    "            else:\n",
    "                return upper * (upper - 1) // 2 + x - upper + 1\n",
    "\n",
    "        def f(mid, n, index, maxSum):\n",
    "            left = index\n",
    "            right = n - index - 1\n",
    "            return g(mid,left)+g(mid,right)+mid <= maxSum\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if f(mid, n, index, maxSum):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "            # print(left, right)\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int: \n",
    "        left = index\n",
    "        right = n - index - 1\n",
    "        if left > right:\n",
    "            left, right = right, left\n",
    "\n",
    "        upper = ((left + 1) ** 2 - 3 * (left + 1)) // 2 + left + 1 + (left + 1) + ((left + 1) ** 2 - 3 * (left + 1)) // 2 + right + 1\n",
    "        if upper >= maxSum:\n",
    "            a = 1\n",
    "            b = -2\n",
    "            c = left + right + 2 - maxSum\n",
    "            return floor(((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a)))\n",
    "\n",
    "        upper = (2 * (right + 1) - left - 1) * left // 2 + (right + 1) + ((right + 1) ** 2 - 3 * (right + 1)) // 2 + right + 1\n",
    "        if upper >= maxSum:\n",
    "            a = 1/2\n",
    "            b = left + 1 - 3/2\n",
    "            c = right + 1 + (-left - 1) * left / 2 - maxSum\n",
    "            return floor(((-b + (b ** 2 - 4 * a * c) ** 0.5) / (2 * a)))\n",
    "\n",
    "        else:\n",
    "            a = left + right + 1\n",
    "            b = (-left ** 2 - left - right ** 2 - right) / 2 - maxSum\n",
    "            return floor(-b / a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            cnt = 0\n",
    "            # 计算左边\n",
    "            if x - index >= 1:\n",
    "                cnt += (x - index + x) * (index + 1) // 2\n",
    "            else:\n",
    "                cnt += (1 + x) * (x) // 2 + (index - (x - 1) - 1) - 0 + 1\n",
    "            # 计算右边\n",
    "            if x - (n - 1 - index) >= 1:\n",
    "                cnt += (x - (n - 1 - index) + x) * (n - 1 - index + 1) // 2\n",
    "            else:\n",
    "                cnt += (1 + x) * (x) // 2 + (n - 1) - (index + (x - 1) + 1) + 1\n",
    "            # 减去重复计算的中间\n",
    "            cnt -= x\n",
    "            return cnt <= maxSum\n",
    "            \n",
    "        # 二分查找\n",
    "        a, b = 1, maxSum\n",
    "        # 维护左边界合法\n",
    "        while a + 1 < b:\n",
    "            c = a + (b - a) // 2\n",
    "            if check(c):\n",
    "                a = c\n",
    "            else:\n",
    "                b = c - 1\n",
    "        if check(b):\n",
    "            return b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(m: int) -> bool:\n",
    "            if m == 0:\n",
    "                 return True\n",
    "            ans = -m\n",
    "            l = index + 1\n",
    "            if m >= l:\n",
    "                x0 = m - (l - 1)\n",
    "                ans += (x0 + m) * l // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + l - m\n",
    "            \n",
    "            r = n - index\n",
    "            if m >= r:\n",
    "                x0 = m - (r - 1)\n",
    "                ans += (x0 + m) * r // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + r - m\n",
    "            return ans <= maxSum\n",
    "        left = 1\n",
    "        right = maxSum + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int: \n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if self.valid(mid, n, index, maxSum):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "    def valid(self, mid: int, n: int, index: int, maxSum: int) -> bool:\n",
    "        left = index\n",
    "        right = n - index - 1\n",
    "        return mid + self.cal(mid, left) + self.cal(mid, right) <= maxSum\n",
    "\n",
    "    def cal(self, big: int, length: int) -> int:\n",
    "        if length + 1 < big:\n",
    "            small = big - length\n",
    "            return ((big - 1 + small) * length) // 2\n",
    "        else:\n",
    "            ones = length - (big - 1)\n",
    "            return (big - 1 + 1) * (big - 1) // 2 + ones\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(m: int) -> bool:\n",
    "            # if m == 0:\n",
    "            #     return True\n",
    "            ans = -m\n",
    "            l = index + 1\n",
    "            if m >= l:\n",
    "                x0 = m - (l - 1)\n",
    "                ans += (x0 + m) * l // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + l - m\n",
    "            \n",
    "            r = n - index\n",
    "            if m >= r:\n",
    "                x0 = m - (r - 1)\n",
    "                ans += (x0 + m) * r // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + r - m\n",
    "            return ans <= maxSum\n",
    "        left = 0\n",
    "        right = maxSum + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        '''\n",
    "        2 3 2 1 1 1\n",
    "        '''\n",
    "        \n",
    "        def check(x, n):\n",
    "            res = 0\n",
    "            left = index - (x - 1)\n",
    "            if left >= 0:\n",
    "                res += (1 + x) * (x) // 2\n",
    "                res += (left)\n",
    "            else:\n",
    "                res += (x + x - index) * (index+1)//2\n",
    "            \n",
    "            right = index + (x - 1)\n",
    "            if right < n:\n",
    "                res += (1 + x) * (x) // 2\n",
    "                res += (n-1-right)\n",
    "            else:\n",
    "                res += (x + x - (n-1-index)) * (n-index) // 2\n",
    "            \n",
    "            res -= x # 多计算了一个x\n",
    "            nonlocal maxSum\n",
    "            return res > maxSum\n",
    "\n",
    "\n",
    "        i, j = 0, 2 * 10 ** 9\n",
    "    \n",
    "        while i < j - 1:\n",
    "            mid = (i+j)//2\n",
    "            if check(mid, n):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid\n",
    "        \n",
    "        if check(i, n):\n",
    "            return i-1\n",
    "        return j - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\r\n",
    "        # 最大化某个值等于二分答案 \r\n",
    "        # 本题存在数学解，但是不好算 \r\n",
    "        def check(x: int) -> bool:\r\n",
    "            pre = 0\r\n",
    "            if index:\r\n",
    "                if x - index > 0:\r\n",
    "                    pre = (x - 1 + x - index) * (index) // 2\r\n",
    "                else:\r\n",
    "                    pre = (x) * (x - 1) // 2 + (index - (x - 1))\r\n",
    "        \r\n",
    "            if x - (n - index - 1) > 0:\r\n",
    "                suf = (x + x - (n - index - 1)) * (n - index) // 2\r\n",
    "            else:\r\n",
    "                suf = x * (x + 1) // 2 + (n - index - x)\r\n",
    "            return pre + suf > maxSum\r\n",
    "\r\n",
    "        # l, r = 1, 10 ** 9 + 5 \r\n",
    "        # while l + 1 < r:\r\n",
    "        #     mid = (l + r) // 2\r\n",
    "        #     if check(mid):\r\n",
    "        #         l = mid\r\n",
    "        #     else:\r\n",
    "        #         r = mid \r\n",
    "        \r\n",
    "        return bisect_left(range(10 ** 9 + 5), True, key=check) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def f(v):\n",
    "            s = 0\n",
    "            if v > index:\n",
    "                s += (v - index + v) * (index + 1) // 2\n",
    "            else:\n",
    "                s += (v + 1) * v // 2 + index - v + 1\n",
    "            if v >= (n - index):\n",
    "                s += (2*v - n + index) * (n - index - 1) // 2\n",
    "            else:\n",
    "                s += v * (v - 1) // 2 + n - index - v\n",
    "            return s <= maxSum\n",
    "        \n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "            if f(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(x):\n",
    "            left, right = max(0, index - x + 1), min(n - 1, index + x - 1)\n",
    "            l_v, r_v = x - (index - left), x - (right - index)\n",
    "            return (left + n - 1 - right + (x + l_v) * (index - left + 1) // 2 + (x + r_v) * (right - index + 1) // 2 - x) <= maxSum\n",
    "\n",
    "        l, r = 1, maxSum\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid): l = mid\n",
    "            else: r = mid - 1\n",
    "        return l    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        # 计算将所有填为1之后剩余的和\n",
    "        maxSum -= n\n",
    "\n",
    "        # 计算最大化坐标到左右的距离\n",
    "        d1 = index\n",
    "        d2 = n - index - 1\n",
    "        if d1 > d2:\n",
    "            d1, d2 = d2, d1\n",
    "\n",
    "        # 计算实现两侧顶满的尖峰所需要的和\n",
    "        peak = (0 + d2) * (d2 + 1) // 2 + ((d2 - d1) + d2) * (d1 + 1) // 2 - d2  # 两个等差数列减被共用的最大值\n",
    "\n",
    "        # 处理剩余可以组成尖峰的情况：尽可能组成尖峰，其余的平均分布\n",
    "        if maxSum >= peak:\n",
    "            # print(\"距离:\", [d1, d2], \"剩余:\", maxSum, \"尖峰需要:\", peak)\n",
    "            return 1 + d2 + (maxSum - peak) // n\n",
    "\n",
    "        # print(\"距离:\", [d1, d2], \"剩余:\", maxSum)\n",
    "\n",
    "        # 不足以组成尖峰的情况：二分查找最大值\n",
    "        left, right = 0, d2\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            need = (0 + mid) * (mid + 1) // 2 + ((mid - min(mid, d1)) + mid) * (min(mid, d1) + 1) // 2 - mid\n",
    "            # print(left, right, \"->\", mid, \"=\", need)\n",
    "            if need <= maxSum:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return 1 + (left - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def total_sum(cnt,x):\n",
    "            return (x+x-cnt+1)*cnt//2 if cnt<=x else (x+1)*x//2+cnt-x \n",
    "        l,r=1,maxSum\n",
    "        while l<r:\n",
    "            m=l+r+1>>1\n",
    "            if total_sum(index,m-1)+total_sum(n-index,m)<=maxSum:\n",
    "                l=m \n",
    "            else:\n",
    "                r=m-1\n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(m: int) -> bool:\n",
    "            # if m == 0:\n",
    "            #     return True\n",
    "            ans = -m\n",
    "            l = index + 1\n",
    "            if m >= l:\n",
    "                x0 = m - (l - 1)\n",
    "                ans += (x0 + m) * l // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + l - m\n",
    "            \n",
    "            r = n - index\n",
    "            if m >= r:\n",
    "                x0 = m - (r - 1)\n",
    "                ans += (x0 + m) * r // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + r - m\n",
    "            return ans <= maxSum\n",
    "        left = 0\n",
    "        right = maxSum + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def sum(x, cnt):\n",
    "            return (x + x - cnt + 1) * cnt // 2 if x >= cnt else (x + 1) * x // 2 + cnt - x\n",
    "\n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if sum(mid - 1, index) + sum(mid, n - index) <= maxSum:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def cal(max_val: int, length: int) -> int:\n",
    "            if max_val <= length:\n",
    "                return (1 + max_val) * max_val // 2 + length - max_val\n",
    "            else:\n",
    "                return (max_val + max_val - length + 1) * length // 2\n",
    "\n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "            numsSum = cal(mid - 1, index) + mid + cal(mid - 1, n - index - 1)\n",
    "            if numsSum > maxSum:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        if n == 1:\n",
    "            return maxSum\n",
    "\n",
    "        def getSum(max_value, arr_length):\n",
    "            if max_value - 1 > arr_length:\n",
    "                return (max_value - 1 + max_value - arr_length) * arr_length // 2\n",
    "            else:\n",
    "                return (max_value - 1 + 1) * (max_value - 1) // 2 + (arr_length - max_value + 1)\n",
    "        \n",
    "        def isValid(max_value):\n",
    "            left_length = index\n",
    "            right_length = n - index - 1\n",
    "            return getSum(max_value, left_length) + getSum(max_value, right_length) + max_value <= maxSum\n",
    "\n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2 + 1\n",
    "            if isValid(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "\n",
    "        def cal(limit):\n",
    "            total = limit\n",
    "            l_num = index\n",
    "            if l_num > 0:\n",
    "                left = limit-l_num\n",
    "                if left >= 1:\n",
    "                    total += (left+limit-1)*l_num//2\n",
    "                else:\n",
    "                    total += (limit-1)*limit//2 + l_num-limit+1\n",
    "            r_num = n-index-1\n",
    "            if r_num > 0:\n",
    "                right = limit-r_num\n",
    "                if right >= 1:\n",
    "                    total += (limit-1+right)*r_num//2\n",
    "                else:\n",
    "                    total += limit*(limit-1)//2 + r_num-limit+1\n",
    "            if total <= maxSum:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        \n",
    "        l, r = 1, maxSum\n",
    "        while l < r:\n",
    "            mid = (l+r+1)//2\n",
    "            if cal(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        l = 1\n",
    "        r = int(1e9)\n",
    "        while l < r:\n",
    "            mid = l + r + 1>> 1\n",
    "            def check():\n",
    "                if mid > index:\n",
    "                    ## total: index\n",
    "                    ## start: mid - 1\n",
    "                    ## end: mid  - index\n",
    "                    t1 = (2*mid - index - 1) * index // 2\n",
    "                else:\n",
    "                    t1 = (index - mid + 1) + (mid) * (mid - 1)//2\n",
    "                if index >= n - mid:\n",
    "                    ## total n - 1 - index\n",
    "                    ## from mid - 1\n",
    "                    ## to mid - n + index - 1\n",
    "                    t2 = (2 * mid - n  + index) * (n - 1 - index)//2\n",
    "                else:\n",
    "                    t2 = mid * (mid - 1)//2 + (n - index - mid)\n",
    "                return t1 + t2 + mid <= maxSum\n",
    "            if check():\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(m: int) -> bool:\n",
    "            if m == 0:\n",
    "                 return True\n",
    "            ans = -m\n",
    "            l = index + 1\n",
    "            if m >= l:\n",
    "                x0 = m - (l - 1)\n",
    "                ans += (x0 + m) * l // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + l - m\n",
    "            \n",
    "            r = n - index\n",
    "            if m >= r:\n",
    "                x0 = m - (r - 1)\n",
    "                ans += (x0 + m) * r // 2\n",
    "            else:\n",
    "                ans += (1 + m) * m // 2 + r - m\n",
    "            return ans <= maxSum\n",
    "        left = 0\n",
    "        right = maxSum + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        left, right = 1, maxSum\n",
    "        while left<right:\n",
    "            mid = (left + right + 1)//2\n",
    "            if self.check(mid, n, index, maxSum):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left\n",
    "\n",
    "    def check(self, mid, n, index, maxSum):\n",
    "        lefts = index + 1\n",
    "        rights = n - (index + 1) + 1\n",
    "        total = mid + self.cal(mid, lefts)+self.cal(mid,rights)\n",
    "        if total<=maxSum:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def cal(self, m, k):\n",
    "        if k>=m:\n",
    "            ones = k - m\n",
    "            return (1 + m - 1) * (m-1) //2 + ones\n",
    "        else:\n",
    "            small = 1 + m-k\n",
    "            return (small + m - 1) * (k-1) // 2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        rest = maxSum - n\n",
    "\n",
    "        l = r = index\n",
    "\n",
    "        while l>0 or r<n-1:\n",
    "\n",
    "            len = r-l+1\n",
    "\n",
    "            if rest >= len:\n",
    "\n",
    "                rest -= len;\n",
    "\n",
    "                ans+=1\n",
    "\n",
    "                l = max(0, l-1)\n",
    "\n",
    "                r = min(n-1, r+1)\n",
    "\n",
    "            else:\n",
    "\n",
    "                break\n",
    "\n",
    "        ans += rest//n\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        # True, True, ..., True, False, ..., False\n",
    "        left_num, right_num = index, n - 1 - index\n",
    "\n",
    "        def cal(x, L):\n",
    "            \"\"\"\n",
    "                x-L, ..., x-2, x-1, x\n",
    "\n",
    "                1, ..., 1, 2, ..., x-1, x\n",
    "            \"\"\"\n",
    "            if x - L >= 1:\n",
    "                small = x - L\n",
    "                return (small + x - 1) * L // 2\n",
    "            else:\n",
    "                ones = L - (x - 1)\n",
    "                return (1 + x - 1) * (x - 1) // 2 + ones\n",
    "\n",
    "        def check(x):\n",
    "            return x + cal(x, left_num) + cal(x, right_num) <= maxSum\n",
    "        \n",
    "        left, right = 1, maxSum\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(x):\n",
    "            if(index < x - 1):\n",
    "                sum1 = (2*x-index-1)*index//2\n",
    "            else:\n",
    "                sum1 = index - x + 1 + (x-1)*x//2\n",
    "            if(n-index < x):\n",
    "                sum2 = (2*x - n + index)*(n-index-1)//2\n",
    "            else:\n",
    "                sum2 = n - index - x + (x-1)*x//2\n",
    "            return sum1 + sum2 + x <= maxSum\n",
    "        left, right = 1, maxSum\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(check(mid)):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, n: int, index: int, maxSum: int) -> int:\n",
    "        def check(num):\n",
    "            sum=0\n",
    "            if num>=index+1:\n",
    "                sum+=((num-index+num)*(index+1))/2\n",
    "            else:\n",
    "                sum+=(index+1-num)+(1+num)*num/2\n",
    "            if n-index>=num:\n",
    "                sum+=(1+num-1)*(num-1)/2+(n-1-index-(num-1))\n",
    "            else:\n",
    "                sum+=(num-1+num-(n-1-index))*(n-index-1)/2\n",
    "            if sum<=maxSum:\n",
    "                return True\n",
    "            return False\n",
    "        left,right=1,maxSum+1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left           \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "   "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
